package com.ry.day1129;

import java.util.HashMap;
import java.util.Map;

public class LC72 {

    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }


    static class Solution {
        /**
         * @param inorder:   A list of integers that inorder traversal of a tree
         * @param postorder: A list of integers that postorder traversal of a tree
         * @return: Root of a tree
         */
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int size = inorder.length;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < size; i++) {
                map.put(inorder[i], i);
            }

            return f(postorder, 0, size - 1, inorder, 0, size - 1, map);
        }

        public TreeNode f(int[] parr, int l2, int r2, int[] inarr, int l3, int r3, Map<Integer, Integer> map) {
            if (l2 > r2) return null;
            if (l2 == r2) return new TreeNode(parr[l2]);
            TreeNode root = new TreeNode(parr[r2]);
            int idx = map.get(parr[r2]);
            root.left = f(parr, l2, l2 + idx - l3 - 1, inarr, l3, idx - 1, map);
            root.right = f(parr, l2 + idx - l3, r2-1, inarr, idx + 1, r3, map);
            return root;
        }

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
72 · 中序遍历和后序遍历树构造二叉树
算法
中等
通过率
37%

题目
题解28
笔记
讨论99+
排名
记录
描述
根据中序遍历和后序遍历树构造二叉树

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


你可以假设树中不存在相同数值的节点

样例
样例 1：

输入：

中序遍历 = []
后序遍历 = []
输出：

{}
解释：

二叉树为空

样例 2：

输入：

中序遍历 = [1,2,3]
后序遍历 = [1,3,2]
输出：

{2,1,3}
解释：

二叉树如下
2
/ \
1    3

相关知识
学习《算法入门：递归》课程中的5.8中序遍历和后序遍历构造二叉树相关内容 ，了解更多相关知识！
标签
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒

        控制台
        历史提交

 */
